package DFS;

import DFS.AdjList;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * @Author: dust
 * @Date: 2019/11/18 15:24
 */
public class Graph implements Cloneable {

    private int V;
    private int E;
    private TreeSet<Integer>[] adj;

    public void validateVertex(int v){
        if(v<0||v>=V)
            throw new IllegalArgumentException("vertex"+v+"is invalid");

    }

    public Graph(String filename) {
        File file=new File(filename);
        try(Scanner scanner=new Scanner(file)){
            V=scanner.nextInt();
            if(V<0)
                throw new IllegalArgumentException("V must be non-negative");
            adj=new TreeSet[V];
            for(int i=0;i<V;i++){
                adj[i]= new TreeSet<>();//java8类型推断
            }
            E=scanner.nextInt();
            if(E<0)
                throw new IllegalArgumentException("E must be non-negative");
            for(int i=0;i<E;i++){
                int a=scanner.nextInt();
                validateVertex(a);
                int b=scanner.nextInt();
                validateVertex(b);

//                判断自环边
                if(a==b)
                    throw new IllegalArgumentException("Self Loop is Detected!");
//                判断平行边
                if(adj[a].contains(b))//o(log V)级别
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                adj[a].add(b);
                adj[b].add(a);
            }
        }catch (IOException e){
            e.printStackTrace();
        }
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public boolean hasEdge(int v,int w){
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }

    public Iterable<Integer> adj(int v){
        validateVertex(v);
        return adj[v];
    }

    public int degree(int v){
        validateVertex(v);
        return adj[v].size();
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append(String.format("V=%d,E=%d\n",V,E));
        for(int i=0;i<V;i++){
            sb.append(String.format("%d :",i));
            for(int w:adj[i]){
                sb.append(String.format("%d ",w));
            }
            sb.append('\n');
        }

        return sb.toString();
    }

    public void removeEdge(int v,int w){

        validateVertex(v);
        validateVertex(w);

        adj[v].remove(w);
        adj[w].remove(v);

    }

    @Override
    public Object clone(){
        try {
            Graph cloned=(Graph)super.clone();
            cloned.adj=new TreeSet[V];
            for(int v=0;v<V;v++){
                cloned.adj[v]=new TreeSet<>();
                for(int w:adj[v]){
                    cloned.adj[v].add(w);
                }
            }
            return cloned;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
       return null;
    }

    public static void main(String[] args) {
        AdjList adjList=new AdjList("g.txt");
        System.out.println(adjList.toString());
    }

}
